Статья 11215

Название статьи

ПОДХОД К РЕШЕНИЮ ПСЕВДОГЕОМЕТРИЧЕСКОЙ ВЕРСИИ ЗАДАЧИ КОММИВОЯЖЕРА 

Авторы

Макаркин Сергей Борисович, доцент, кафедра прикладной математики и информатики, Тольяттинский государственный университет (Россия, г. Тольятти, ул. Белорусская, 14), s.makarkin@gmail.com
Мельников Борис Феликсович, доктор физико-математических наук, профессор, кафедра прикладной математики и информатики, Тольяттинский государственный университет (Россия, г. Тольятти, ул. Белорусская, 14), barmaley62@yandex.ru
Тренина Марина Анатольевна, старший преподаватель, кафедра прикладной математики и информатики, Тольяттинский государственный университет (Россия, г. Тольятти, ул. Белорусская, 14), trenina.m.a@gmail.com

Индекс УДК

004.23

Аннотация

Актуальность и цели. Задача коммивояжера является примером математической модели, которая, будучи созданной для одной предметной области, находит свое применение и во многих других областях. Псевдогеометрическая версия этой проблемы более адекватно описывает множество ее частных случаев, встречающихся в большинстве предметных областей, чем значительно более распространенная геометрическая версия. Цель работы: применить разработанные подходы для решения геометрической версии задачи коммивояжера для ее так называемой псевдогеометрической версии.
Материалы и методы. Для решения псевдогеометрической задачи коммивояжера рассматривается несколько случайно сгенерированных перестановок всего множества точек, и для каждой из них применяется алгоритм псевдовосстановления их расположения. Выбор единственного варианта расположения каждой точки возможен после решения оптимизационной задачи, заключающейся в повороте сгенерированного множества точек на некоторый угол и смещении на некоторый вектор.
Результат. Сформулированы различные метрики и изучены их свойства, на основании которых разработан эвристический алгоритм локального поиска.
Выводы. Применение описанных в настоящей работе метрик и эвристического алгоритма локального поиска позволило повысить эффективность геометрического метода решения псевдогеометрической задачи коммивояжера.

Ключевые слова

задача коммивояжера, геометрическая версия, псевдогеометрическая версия, геометрический подход, метрика, эвристические алгоритмы.

Скачать статью в формате PDF
Список литературы

1. Макаркин, С. Б. Геометрические методы решения псевдогеометрической версии задачи коммивояжера / С. Б. Макаркин, Б. Ф. Мельников // Стохастическая оптимизация в информатике. – 2013. – Т. 9, № 2. – С. 54–72.
2. Макаркин, С. Б. Применение проблемно ориентированных метрик в геометрических алгоритмах решения псевдогеометрической версии задачи коммивояжера / С. Б. Макаркин, Б. Ф. Мельников, М. А. Тренина // Стохастическая оптимизация в информатике. – 2014. – Т. 10, вып. 1. – С. 63–71.
3. Hromkovic, J. Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics / J. Hromkovic. – Springer, 2003. – 538 p.
4. Melnikov, B. Some special heuristics for discrete optimization problems / B. Melnikov, A. Radionov, V. Gumayunov//Proc.of 8th International Conference on EnterpriseInformationSystems,ICEIS-2006.-P.360-364.
5. Мельников, Б. Еще раз об эвристиках для задачи коммивояжера / Б. Мельников, Н. Романов // Теоретические проблемы информатики и ее приложений. –2001. – № 4. – С. 81–92.
6. Melnikov, B. Multiheuristic approach to discrete optimization problems / B. Melnikov // Cybernetics and Systems Analysis. – 2006. – Vol. 42, № 3 (Sept.). – P. 335–341.
7. Мельников, Б. Ф. Кластеризация ситуаций в алгоритмах реального времени для задач дискретной оптимизации / Б. Ф. Мельников, Е. А. Мельникова // Системы управления и информационные технологии. – 2007. – № 2 (28). – С. 16–20.
8. The Traveling Salesman problem / G. Gutin, A. Punnen (editors). – Kluwer Academic Publishers, 2002.
9. URL: http://arxiv.org/ftp/arxiv/papers/1204/1204.2350.pdf – Liew Sing. Introducing convex layers to the Traveling Salesman Problem / Preprint: arXiv: 1204.2348. –2012. – Режим доступа – свободный. (Access mode – free.)
10. Somhom, S. Competition-based neural network for the multiple travelling salesmen problem with minimax objective / S. Somhom, A. Modares, T. Enkawa // Computers & Operations Research. – 1999. – Vol. 26, №. 4. – P. 395–407.
11. Громкович, Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию : пер. с нем. / Ю. Громкович. – СПб. : БХВ-Петербург, 2010. – 326 с.
12. Колмогоров А. Н. Элементы теории функций и функционального анализа /А. Н. Колмогоров, С. В. Фомин ; МГУ им. М. В. Ломоносова. – Изд. 7-е. – М. :Физматлит, 2004. – 570 с.

 

Дата создания: 31.07.2015 11:50
Дата обновления: 20.10.2015 15:02